package com.alu.basic;

import static org.junit.Assert.assertEquals;
import org.junit.Test;

/**
 * 二分法查找
 * 
 * @author Administrator
 *
 */
public class BinarySearch {
	
	private int search(int key, int[] arr) {
		
		// 设置高位和低位
		int low = 0;
		int high = arr.length-1;
		
		// 只要低位没有超出高位，就继续寻找
		while(low <= high) {
			// 中间位，注意偏移
			int mid = low + (high-low)/2;
			
			if(key > arr[mid])
				low = mid+1;
			else if(key < arr[mid])
				high = mid-1;
			else
				return mid;
		}
		
		return -1;
	}
	
	@Test
	public void test() {
		assertEquals(1, search(5, new int[]{4,5,6,7,8,9,10}));
		assertEquals(2, search(6, new int[]{4,5,6,7,8,9,10}));
		assertEquals(0, search(4, new int[]{4,5,6,7,8,9,10}));
		assertEquals(6, search(10, new int[]{4,5,6,7,8,9,10})); 
		assertEquals(-1, search(50, new int[]{4,5,6,7,8,9,10})); 
	}
}
